1. Field of the Invention
This invention relates generally to a method for generating, updating and extending digital maps, such as digital vector maps, using probe data, and more generally toward a method for improving data mining activities using advanced time models.
2. Related Art
Navigation systems, electronic maps (also known as digital maps), and geographical positioning devices are increasingly used by travelers to assist with various navigation functions, such as to determine the overall position and orientation of the traveler and/or vehicle, find destinations and addresses, calculate optimal routes, and provide real-time driving guidance. Typically, the navigation system includes a small display screen or graphic user interface that portrays a network of streets as a series of line (or road) segments. The traveler can be generally located on the digital map close to or with regard to a road or street.
Digital maps are expensive to produce and update, since collecting and processing road information is very costly. Surveying methods or digitizing satellite images are commonly employed techniques for creating a digital map. Furthermore, digital maps are likely to contain inaccuracies or systematic errors due to faulty or inaccurate input sources or flawed inference procedures. Once a digital map has been created, it is costly to keep map information up to date, since road geometry changes over time. In some regions of the world, digital maps are not available at all.
It may be the case that an existing roadway map or network is incomplete in its depiction of all roadways or paths within a given region. Furthermore, due to the evolving nature of networks which may include but are not limited to roadways and paths, changes may occur over time such that an existing digital map may no longer accurately portray current conditions.
In recent years, probe data (also commonly referred to as “probe traces”) has been used to create and update digital maps of transportation networks, e.g. navigable systems of roads, pedestrian walkways, paths, rivers, shipping lanes or other networks that can be used to transport humans or vehicles. Probe traces are a plurality of sequential location measurements from location sensors housed in a plurality of vehicles or carried by a plurality of pedestrians. For example, the location sensors can be satellite navigation signal receivers, e.g. GPS systems.
One class of algorithms used generating networks from probe data are known as incremental algorithms. Incremental algorithms have several advantages, although other non-incremental network generation algorithms are also useful and sometimes preferred. One primary advantage of incremental algorithms is that an incremental approach allows extending and improving a network without need to process the whole network again. Examples of incremental map generation algorithms can be found in U.S. Pat. No. 6,385,539 and in the Applicant's co-pending PCT application titled “INCREMENTAL MAP GENERATION, REFINEMENT AND EXTENSION WITH GPS TRACES” by inventor H. Mund (PCT/EP2009/063938 filed 22 Oct. 2009). The techniques described in this latter PCT application are referred to hereafter as the Viae Novae algorithm.
It is known from the Viae Novae algorithm, for example, to take probe data inputs from low-cost positioning systems and handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally learning a map using certain clustering technologies. The input to be processed consists of recorded GPS traces in the form of, for example, a standard ASCII stream, which is supported by almost all existing GPS devices. The output is a road map in the form of a directed graph with nodes and edges annotated with travel time information. Travelers appropriately fitted with navigation devices and traversing a main trunk and/or branch junction may thus create a trace map, with nodes created at regular distances. The nodes and edges are stored in a digital vector map table or database. Through this technique which represents an incremental approach, road geometry can be inferred, and the collected data points refined by filtering and partitioning algorithms.
FIG. 1 describes this exemplary incremental approach in terms of a simplified flow process. A plurality of probes 14 are depicted as GPS-enabled personal navigation devices such as those manufactured by TomTom NV (www.tomtom.com). However, any suitable device with GPS functionality may be used to generate probe data points, including handheld devices, mobile phones, PDAs, and the like. The probe data points may be collected and stored in a probe data table 16 or other suitable database or repository. The existing digital vector map, in this example a previously created digital map, is contained in a table 18. Of course, the digital vector map 18 can exist as a database or in other suitable form. Trace lines are generated from the rough probe data in table 16 as an initial step. A new line is selected from the probe data table at step 20. The selected line is matched to the digital vector map at step 22. During this step, each point of the trace line will be associated with a network element using a suitable map matching method. If the matching method is not able to associate any network element to the trace line, the probe data point is marked as “unmatched.” All other probe data points are attempted to be matched to the existing network in this manner. For trace line segments whose data points are not matched to any element of the existing network, these must be split from the network elements and inserted, i.e., connected, via a new or existing junction. This occurs in step 24. In some cases, it is reasonable to use a known or pre-existing junction. Junctions may be referred to as intersections in a roadway network application. Once the matching and junction steps 22, 24 have been completed, the trace line segments are merged with the associated network elements at step 26. This may be accomplished with merge suitable algorithms and methodology. Finally, to reduce the number of shape points, it is possible to simplify the network element before updating the network table at step 18. This optional simplification step is indicated at function block 28 and can be accomplished through various techniques, including by application of the well-known Douglas-Peucker algorithm.
New trace data which are available can be used in this manner to easily refine and extend a road network in a digital map system. When using an incremental approach as described above, it is not possible to remove old data from the generated road network. A problem, however, lies in that the remnant of old, possibly outdated, trace data will be factored into the incremental algorithms when analyzing the extent to which a network is to be extended or improved, and thus continue to exert influence over the analysis. The usage and importance of a road element is described by its weight value. If a road segment is not in use anymore, it may have still a high weight and therefore continue to negatively influence the map refinement and extension exercises.
Accordingly, there is a need for an improved method for updating and extending digital vector maps using probe or trace data, and that is not susceptible to the negative influence of old, possibly outdated, trace data. The method should be useful in conjunction with both incremental and non-incremental network generation algorithms.